public class Sort {
    public void zhijiecharu(int[] arr){
        for(int i=1;i<arr.length;i++){
            int tmp=arr[i];
            int j=i-1;
            for(;j>=0;j--){
                if(arr[j]>tmp){
                    arr[j+1]=arr[j];
                }else{
                    arr[j+1]=tmp;
                    break;
                }
            }
            arr[j+1]=tmp;
        }

    }
    public void xierpaixu(int [] arr){
        int gap=arr.length;
        while(gap>1){
            //gap的最后取值一定要是0
            gap=gap/2;
            xierpaixu1(arr,gap);
        }
    }
    public void xierpaixu1(int[] arr,int gap){
        for(int i=gap;i<arr.length;i=i+gap){
            int tmp=arr[i];
            int j=i-gap;
            for(;j>=0;j=j-gap){
                if(arr[j]>tmp){
                    arr[j+gap]=arr[j];
                }else{
                    arr[j+gap]=tmp;
                    break;
                }
            }
            arr[j+gap]=tmp;
        }
    }
    public void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    public void xuanzepaixu(int[] array){
        for(int i=0;i<array.length;i++){
            int minIndex=i;
            for(int j=i+1;j<array.length;j++){
                if(array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    public void xuanzepaixu1(int[] array){
        int left=0;
        int right=array.length-1;
        while(left<right){
            int minIndex=left;
            int maxIndex=left;
            for(int i=left+1;i<array.length;i++){
                if(array[i]<array[minIndex]){
                    minIndex=i;
                }
                if(array[i]>array[maxIndex]){
                    maxIndex=i;
                }
            }
            swap(array,left,minIndex);
            //注意当left=maxIndex时
            if(left==maxIndex){
                maxIndex=minIndex;
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }

    }

    public void createHeap(int[] array){
        //创建堆
        for(int parent=(array.length-1-1)/2;parent>=0;parent--){
            siftDown(array,parent,array.length);
        }

    }
    private void siftDown(int[] array, int parent, int length) {
        //创建大根堆
        int child=2*parent+1;
        while(child<length-1){
            //找左右子树最大值
            if(child+1<length-1&&array[child]<array[child+1]){
                child++;
            }
            if(array[parent]<array[child]){
                swap(array,parent,child);
                child=parent;
                child=2*child+1;
            }else{
                break;
            }
        }
    }
    public void Heapsort(int[] array){
        //从小到大排，必须要是大根堆
        createHeap(array);
        int end=array.length-1;
        while(end>0){
            swap(array,0,end);
            //则最后一个元素一定是最大的
            siftDown(array,0,end);
            end--;
        }

    }
    public void bubble_sort(int[] array){
        for(int i=0;i<array.length-1;i++){
            boolean flg=false;
            for(int j=0;j<array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg=true;
                }
            }
            if(!flg){
                break;
            }
        }
    }
    public void quicksort(int[] array){
        quick(array,0,array.length-1);

    }

    private void quick(int[] array, int start, int end) {
        //1.递归终止条件
        if(start>=end){
            return;
        }
        if(end-start+1<=3){
            //这里直接使用快直接插入处理了
            zhijiecharuRange(array,start,end);
            return;
        }
        //使用三数取中法优化
        int minIndex=getMid(array,start,end);
        swap(array,start,minIndex);
        int pivot=wakong(array,start,end);
//        int pivot=hoare(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }

    private int getMid(int[] array, int left, int right) {
        int minindex=(left+right)/2;
        if(array[left]<array[right]){
            if(array[minindex]<array[left]){
                return left;
            }else if(array[minindex]>array[right]){
                return right;
            }else{
                return minindex;
            }
        }else{
            if(array[minindex]>array[left]){
                return left;
            }else if(array[minindex]<array[right]){
                return right;
            }else{
                return minindex;
            }
        }
    }

    private void zhijiecharuRange(int[] array, int start, int end) {
        for(int i=start+1;i<=end;i++){
            int tmp=array[i];
            int j=i-1;
            for(;j>=start;j--){
                if(array[j]>array[i]){
                    array[i]=array[j];
                }else{
                    array[i]=tmp;
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

    private int wakong(int[] array, int left, int right) {
        int tmp=array[left];
        while(left<right){
            while(left<right&&array[right]>=tmp){//注意 这里面也要写left<right,防止越界
               right--;
            }
            array[left]=array[right];
            while(left<right&&array[left]<=tmp){
               left++;
            }
            array[right]=array[left];
        }
        array[left]=tmp;
        return left;
    }
    private int hoare(int[] array,int left,int right){
        int tmp=array[left];
        int tmpLeft=left;
        while(left<right){
            while(left<right&&array[right]>=tmp){
                right--;
            }
            while(left<right&&array[left]<=tmp){
                left++;
            }
            //等两个找到才换，与挖空法注意区分
            swap(array,left,right);
        }
        swap(array,tmpLeft,left);
        return left;
    }
    public static void mergeSort(int[] array) {
        mergeSortTmp(array,0,array.length-1);

    }

    private static void mergeSortTmp(int[] array,int left,int right) {
        //先分解，再合并
        while(left>=right){
            return;
        }
        int mid=(left+right)/2;
        mergeSortTmp(array,left,mid);
        mergeSortTmp(array,mid+1,right);
        //合并数组
        merge(array,left,mid,right);
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int[] tmp=new int[right-left+1];
        int k=0;
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        //确保两个数组都有元素和防止越界
        while(s1<=e1&&s2<=e2){
            if(array[s1]>array[s2]){
                tmp[k++]=array[s2++];
            }else{
                tmp[k++]=array[s1++];
            }
        }
        //因为可能有多个元素
        //则s2的元素全都放置到了tmp数组里面
        while(s1<=e1){
            tmp[k++]=array[s1++];
        }
        while(s2<=e2){
            tmp[k++]=array[s2++];
        }
        //讲tmp数组写到array里面
        for(int i=0;i<k;i++){
            array[i+left]=tmp[i];
        }

    }
    public void jishupaixu(int[] array){
        //1.在待排序的元素中找出数组的最大值和最小值
        int max=array[0];
        int min=array[0];
        for(int i=1;i<array.length;i++){
            if(array[i]>max){
                max=array[i];
            }
            if(array[i]<min){
                min=array[i];
            }
        }
        //创建count数组去计数
        //遍历待排序的数组，计数放入count中
        int len=max-min+1;
        int[] count=new int[len];
        for(int i=0;i<array.length;i++){
            int index=array[i]-min;
            count[index]++;
        }
        //依次遍历计数数组
        int index=0;
        for(int i=0;i<len;i++){
            while(count[i]!=0){
                array[index]=i+min;
                index++;
                count[i]--;
            }
        }
    }

}
